package com.hehao.java_basic.algorithm.排序;

import com.alibaba.fastjson2.JSON;
import org.junit.Test;
import org.junit.runner.RunWith;
import org.springframework.boot.test.context.SpringBootTest;
import org.springframework.test.context.junit4.SpringRunner;

/**
 * @author Damon
 * @date 2023/2/8
 * 常见排序算法Demo
 * 插入排序：【直接插入、shell排序】
 * 选择排序：【直接选择、堆排序】
 * 交换排序：【冒泡排序、快速排序】
 * 归并排序
 * 基数排序
 */
@SpringBootTest(classes = SortTest.class)
@RunWith(SpringRunner.class)
public class SortTest {
    //private Integer[] arr = {70,10,2,60,51,28,10};
    //private int[] arr = {20, 40, 30, 10, 60, 50};
    private final int[] arr = {8, 4, 5, 7, 1, 3, 6, 2};
    private final int n = arr.length;
    private int i, j;

    /**
     * 冒泡排序基础版(将相邻两个元素对比，所以最多的对比次数是数组长度-1次)
     */
    @Test
    public void bubbleSort() {

        for (i = n - 1; i > 0; i--) {  //外层控制要循环的数组次数即控制数组下标的减少
            for (j = 0; j < i; j++) {  //内层只需比较外层最大下标的数组内元素进行冒泡排序就ok
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
        System.out.println("========😉😉😉" + JSON.toJSONString(arr));

    }

    /**
     * 冒泡排序升级版(外层循环可能精简)
     */
    @Test
    public void bubbleSortPlus() {
        for (int i = n - 1; i > 0; i--) {
            boolean flag = true;
            for (int j = 0; j < i; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    flag = false;
                }
            }
            if (flag) {
                break;
            }
        }
        System.out.println("========" + JSON.toJSONString(arr));
    }

    /**
     * 归并排序
     */
    @Test
    public void mergeSort() {
        int[] temp = new int[arr.length];
        splitAndMergeSort(arr, 0, arr.length - 1, temp);
        System.out.println("========归并后数组========" + JSON.toJSONString(arr));
    }

    /**
     * 归并排序的拆分方法
     * @param arr 待排序原数组
     * @param left 待排序原数组起始索引下标
     * @param right 待排序原数组结束索引下标
     * @param temp 临时保存数据数组
     */
    public static void splitAndMergeSort(int[] arr, int left, int right, int[] temp) {
        if (left < right) {
            int mid = (left + right) / 2;
            //递归拆分左边的数组
            splitAndMergeSort(arr, left, mid, temp);
            //递归拆分右边的数组
            splitAndMergeSort(arr, mid + 1, right, temp);
            merge(arr, left, mid, right, temp);
        }


    }

    /**
     * 归并排序的合并方法
     * @param arr   待排序原数组
     * @param left  拆分后左边数组的起始索引下标
     * @param mid   拆分的索引下标
     * @param right 拆分后左边数组的结束索引下标
     * @param temp  临时保存数据数组
     */
    private static void merge(int[] arr, int left, int mid, int right, int[] temp) {
        //初始化左边数组的的起始下标
        int i1 = left;
        //初始化左边数组的的起始下标
        int j1 = mid + 1;
        //初始化暂存数组的的起始下标
        int t1 = 0;
        //当两个数组都能同时迭代
        while (i1 <= mid && j1 <= right) {
            //1.对比左右两个数组每个下标的元素，存入暂存数组
            if (arr[i1] <= arr[j1]) {
                temp[t1] = arr[i1];
                i1++;
                t1++;
            } else {
                temp[t1] = arr[j1];
                j1++;
                t1++;
            }
        }
        //2.左边数组如果还剩下元素处理
        while (i1 <= mid) {
            temp[t1] = arr[i1];
            i1++;
            t1++;
        }
        // 右边数组如果还剩下元素处理
        while (j1 <= right) {
            temp[t1] = arr[j1];
            j1++;
            t1++;
        }
        //初始化暂存数组下标
        t1 = 0;
        int tempLeft = left;
        //3.从暂存数组对原数组进行已合并元素复制，最后一次暂存数组才是排序完整的
        while (tempLeft <= right) {
            arr[tempLeft] = temp[t1];
            t1++;
            tempLeft++;
        }
    }


}
